package leetcode;

import java.util.Iterator;
import java.util.TreeSet;

import util.Prime;


public class UglyNumber {

	public static void main(String[] args) {
		UglyNumber object = new UglyNumber();
		// int number = Integer.MIN_VALUE;
		
		// System.out.println(object.isUgly(number));
//		for(int i = 1; i < 20; i++){
//			System.out.println(object.nthUglyNumber(i));
//		}
		System.out.println(object.nthUglyNumber(17));
	}
	
	public boolean isUgly(int num) {
        if(num <= 0){
            return false;
        }
        if(num == 1){
            return true;
        }
        while(num > 1){
            if(num % 2 == 0){
                num >>= 1;
            }else if(num % 3 == 0){
                num /= 3;
            }else if(num % 5 == 0){
                num /= 5;
            }else{
                return false;
            }
        }
        return num == 1;
    }
	
	//找到第n个丑数
	//这个解法是使用了TreeSet来进行排序，删除重复元素等工作
	//将第n个元素装进TreeSet之后，然后移除前面的来找到第n个
	//时间复杂度应该是O(2 * nlogn), Runtime : 91 ms
	public int nthUglyNumber(int n) {
		if(n <= 0){
			return 0;
		}
		if(n == 1){
			return 1;
		}
        TreeSet<Long> set = new TreeSet<>();
        //1是第一个丑数
        set.add(1L);
        int count = 1;
        int removeCount = 0;
        int allCount = 2 * n;
        //判断是否加入成功
        boolean flag = false;
        
        //我们是按照*2、*3、*5的顺序加入数的
        //可能下一个数* 2 < 这个数 * 3(* 5)
        //所以我这里判断的条件是count < allCount;
        //比如 1 2 3 5
        //之后加入  2 * 2 = 4  、6 、10
        //但是3 * 3 = 9 < 10,所以不能当count = n的时候就退出
        //此外,还有要注意溢出的问题我们加入的元素时n的两倍，(可以证明,此时一定是按照顺序拍好的)
        //所以我们还需要判断removeCount要小于n - 1，不是小于n
        //因为小于n的退出条件是等于n,而我们要求的是第n个，若把n给移除了，结果就不会了
        //比如n = 17
        while(removeCount < (n - 1) && count < allCount){
        	long first = set.first();
        	set.remove((Long)first);
        	System.out.println("first : " + first);
        	flag = set.add(first * 2);
        	if(flag){
        		count++;
        	}
        	flag = set.add(first * 3);
        	if(flag){
        		count++;
        	}
        	flag = set.add(first * 5);
        	if(flag){
        		count++;
        	}
        	removeCount++;
        	System.out.println("count: " + count + " removeCount: " + removeCount);
        }
        Iterator<Long> iterator = set.iterator();
        int desirePosition = n - removeCount - 1;
        while(iterator.hasNext() && desirePosition > 0){
        	iterator.next();
        	desirePosition--;
        }
        long res = iterator.next();
        return (int)res;
    }

	
	//还有一个很自然的解法，就是所有的Ugly number都是 
	//1 * 2, 2 * 2, 3 * 2, 4 * 2, 5 * 2....
	//1 * 3, 2 * 3, 3 * 3, 4 * 3, 5 * 3....
	//1 * 5, 2 * 5, 3 * 5, 4 * 5, 5 * 5....
	//那么我们每一步都选择最小的
	//时间复杂度O(n) Runtime: 12 ms
	public int nthUglyNumber_2(int n) {
		if( n <= 0){
			return -1;
		}
        int[] ugly = new int[n];
        ugly[0] = 1;
        int index2 = 0, index3 = 0, index5 = 0;
        int factor2 = 2, factor3 = 3, factor5 = 5;
		for (int i = 1; i < n; i++) {
			int min = Math.min(Math.min(factor2, factor3), factor5);
			ugly[i] = min;
			if (factor2 == min)
				factor2 = 2 * ugly[++index2];
			if (factor3 == min)
				factor3 = 3 * ugly[++index3];
			if (factor5 == min)
				factor5 = 5 * ugly[++index5];
		}
        return ugly[n-1];
    }
}
